This invention relates to a statistical data compression/decompression method and, more particularly, to a statistical data compression/restoration method for variable-length encoding of a source character using the probability that the source character will appear following a previous character string (context) of n characters or for decoding of such a variable-length code to a character.
The rapid progress that has recently been made in the development of computers has been accompanied by the need to handle large quantities of data within computers. These data are compressed to shorten transmission time or utilize memory more efficiently.
Various coding methods for compressing data are known. One of these methods is coding that can be adapted to a variety of data, i.e., coding that is not limited to data such as character codes, vector information and images. Such coding is referred to as "universal coding." Example of universal coding are dictionary coding, which utilizes the similarity of character strings, and statistical coding, which utilizes the frequency of appearance of characters. In the discussion that follows, which is based upon information theory, one unit of a word of data shall be referred to as a "character" and a series of any of such word units shall be referred to as a "character string".
Statistical compression is a method which, in accordance with the statistical frequency of appearance (probability of appearance) of compressed data, obtains compressed data by assigning short code lengths to characters having a high probability of appearance. Typical examples of statistical coding are (1) arithmetic coding (e.g., "Arithmetic Coding for Data Compression", by Ian H. Witten, et al., Commun. of ACM Vol. 130, No. 6P, 520-540, or "An Adaptive Dependence Source Model for Data Compression Scheme", by D. M. Abrahamson, Commun. of ACM Vol. 132 No. 1, P77-82), and (2) Huffman coding (e.g., "Dynamic Huffman Coding", by Donald E. Knuth, Journal of Algorithms, Vol. 6, P163-180).
In Huffman coding, a code (the Huffman code) is used as the code of each character, where the Huffman code has a code length that is inversely proportional to the frequency of appearance of the character. Before the details of Huffman coding are discussed, a code tree, which is the structure of data used when a Huffman code is generated, will be described.
FIG. 18 shows an example of a Huffman tree. The points indicated by the circles and squares are nodes. The segments connecting nodes are referred to as "branches" and the node located at the uppermost position is referred to as a "root". An underlying mode Y connected to a certain node X is referred to as the "child" of the node X. Conversely, the node X is referred to as the "parent" of the node Y. A node that does not have a "child" is referred to as a "leaf". Each leaf has a character corresponding to it. Nodes other than "leaves" are referred to as "internal nodes". The number of branches from the "root" to a node is referred to as the "level" of that node.
When encoding is performed using a code tree, the path from the "root" to the "leaf" correlated with the character to be encoded is outputted as a code. More specifically, "1" is outputted when the path branches to the left of each node from the "root" to the target "leaf", and "0" is outputted when the path branches to the right of each node from the "root" to the target "leaf." For example, in the code tree illustrated in FIG. 18, the code "00" is outputted for the character A, which has been correlated with the "leaf" of node number 7, and the code "011" is outputted for the character B, which has been correlated with the "leaf" of node number 8. At decoding, the character outputted is that correlated with the "leaf" reached when nodes are traced in reverse in accordance with the value of each bit of data to be decoded.
In accordance with Huffman coding, a code tree of the above-mentioned kind is generated through the following procedure (referred to as the "Huffman algorithm") (see FIG. 19).
(1) A node (a leaf initially) corresponding to each character is prepared and the frequency of appearance of the corresponding character is recorded in advance for each node. PA1 (2) One new node is created for two nodes having the lowest frequency of appearance, and the node created is connected to the two original nodes by branches. The sum of the frequencies of appearance of the two original nodes connected to the new node by the branches is recorded as the frequency of appearance of this newly created node. PA1 (3) One new node is created for two nodes having the next lowest frequency of appearance, and the node created is connected to the two original nodes by branches. The sum of the frequencies of appearance of the two original nodes connected to the new node by the branches is recorded as the frequency of appearance of this newly created node. Step (3) is continued until there are no longer any nodes having a parent. PA1 (1) If the first character "c" is entered under these conditions, the probability of appearance of "c" is encoded and outputted and the probability of appearance of "c" is updated. PA1 (2) If the second character "a" is entered, the probability of appearance of "a" is encoded and outputted and the probability of appearance of "a" is updated because the context (ca) that can be used in the encoding of "a" has not yet been registered. Further, the character "a" is connected under the immediately preceding character "c" and the context "ca" is registered. PA1 (3) If the third character "c" is entered, the probability of appearance of "c" is encoded and outputted and the probability of appearance of "c" is updated because the context (cac, ac) that can be used in the encoding of "c" has not yet been registered. Further, the character "c" is connected under the immediately preceding character "a" and the context "ac" is registered. PA1 (4) If the fourth character "b" is entered, the probability of appearance of "b" is encoded and outputted and the probability of appearance of "b" is updated because the context (cac, acb, cb) that can be used in the encoding of "b" has not yet been registered. Further, the character "b" is connected under the immediately preceding character "c" and the context "cb" is registered. PA1 (5) If the fifth character " c" is entered, the probability of appearance of "c" is encoded and outputted and the probability of appearance of "c" is updated because the context (cacbc, acbc, cbc, bc) that can be used in the encoding of "c" has not yet been registered. Further, the character "c" is connected under the immediately preceding character "b" and the context "bc" is registered. PA1 (6) If the sixth character "a" is entered, the probability p(a/c) of appearance of context "ca" is encoded and outputted and the probability of appearance of context "ca" is updated because the context "ca" that can be used in encoding has been registered. Further, the context "ca" is connected under the immediately preceding character "b" of the above-mentioned context and the context "bca" is registered. Thereafter, and in similar fashion, this method of sequential registration is used to extend context one degree at a time whenever a character is entered. PA1 F PA1 FU PA1 UJ PA1 JI PA1 IT PA1 TS PA1 SU PA1 F PA1 FU PA1 FUJ PA1 UJI PA1 JIT PA1 ITS PA1 TSU PA1 F PA1 FU PA1 FUJ PA1 FUJI PA1 UJIT PA1 JITS PA1 ITSU PA1 (1) The number of times each context appears diminishes. This leads to a systematic error. PA1 (2) The number of context variations increases. Registering all of these variations is impossible in terms of memory. PA1 (3) Searching for context takes time.
In the code tree generated through this procedure, each character is assigned a code having a code length that is inversely proportional to the frequency of appearance of this character. If encoding is performed using this code tree, therefore, the data will be compressed. There are two kinds of Huffman coding: static, in which the Huffman tree is fixed, and adaptive, in which the coding tree is modified in conformity with the frequency of appearance of each character.
When one character is encoded in accordance with the Huffman coding scheme, a code comprising a whole-number of bits is generated. With arithmetic coding, on the other hand, a fractional number of bits can be assigned to one character. In arithmetic coding, an interval [indicated by (0,1) below] of values greater than 0 but less than 1 grows successively narrower in conformity with the probability of occurrence (frequency of appearance) of each character constituting the source data to be encoded. When the processing of all pixels is finished, a numerical value representing one point in the narrowed interval is outputted as the code.
By way of example, assume that characters to be encoded are the five characters a, b, c, d and e, and that the probabilities that these characters will occur are 0.2, 0.1, 0.05, 0.15 and 0.5, respectively. In such case, intervals having interval widths conforming to these probabilities of occurrence are assigned to the respective characters, as shown in FIG. 20. If a source character string to be encoded is "abe", then the interval (0,1) is first narrowed to the interval (0,0.2) with regard to the character "a", as shown schematically in FIG. 21. Next, the interval (0,0.2) is partitioned into intervals conforming to the probabilities of occurrence of each of the characters, and the interval (0.04,0.06), which corresponds to the next character "b", is selected as the interval of the character string "ab". This interval (0.04,0.06) is then partitioned into intervals conforming to the probabilities of occurrence of each of the characters, and the interval (0.05,0.06), which corresponds to the next character "e", is selected as the interval of the character string "abe". Finally, a sequence of bits below the decimal point obtained when the position of any point (e.g., the lower limit) in this interval is expressed by a binary number is outputted as the encoded result.
In order to achieve better compression with probabilistic statistical coding, the probability of occurrence of each character is obtained in correlation with a character string (context) that has appeared immediately prior to the source character to be encoded. In this case, as shown in FIG. 22, encoding is implemented by an apparatus having a context acquisition unit (context registration unit) 1 and a variable-length encoder 2. The context acquisition unit 1 stores a character string (context) that has appeared and counts the number of these appearances using a context tree of the kind shown in FIG. 23, and obtains a conditional probability of appearance (referred to simply as "probability of appearance" below), which indicates the probability that each character will appear after a certain context. The variable-length encoder 2 generates a code having a length conforming to the probability of appearance obtained by the context acquisition unit 1. It should be noted that when a code is generated, the variable-length encoder 2 uses the probability of appearance that prevailed prior to updating.
By way of example, assume that the context "abc" has not yet been registered (but that the context "ab" has been registered) in FIG. 23. If the source character "c", namely the character to be encoded, has been entered following "ab" under these circumstances, as shown in FIG. 24, the variable-length encoder 2 checks to see whether the context "abc" has been registered or not. Since "abc" has not yet been registered in this case, the variable-length encoder 2 checks to determine whether the context "bc", which is smaller by one character, has been registered. Since the context "bc" has been registered, the variable-length encoder 2 uses the probability P(c/b) of appearance of "bc" to encode the source character "c" by means of arithmetic coding. Further, the context acquisition unit 1 re-calculates and stores the probability P(c/b) of appearance of the context "bc", connects the source character "c" with the context "ab" and then calculates and stores the probability P(c.vertline.a,b) of appearance that the source character "c" will appear following the context "ab". When the source character "c" subsequently reappears following "ab", the variable-length encoder 2 uses the probability P(c.vertline.a,b) of appearance of the context "abc" to encode the source character "c" by arithmetic coding, re-calculates the probability P(c.vertline.a,b) of appearance of the context "abc" and stores the same. Similar processing is then executed to register context and perform variable-length coding using the context registered.
Methods shown in FIGS. 25A, 25B can be used as context-tree registration methods. A context tree may be registered using either method. Neither need possess a tree structure, as in the manner of a hash table or the like. In FIGS. 25A and 25B , a context tree is constructed by successively registering secondary context comprising two characters immediately preceding the source character and the source character. FIG. 25A illustrates a context tree in which the first character of secondary context is connected to the "root" in a case where the character string "cacbcaaabca" has been entered, and FIG. 25B illustrates a context tree in which the last character of secondary context is connected to the "root" in a case where the character string "cacbcaaabca" has been entered.
There are a variety of specific processing procedures that can be used in processing for registering context. These can be broadly divided into procedures in which the degree of context (the number of characters of context) is fixed and procedures in which the degree of context is not fixed (blended context). (For example, see "Modeling for Text Compression", by Timothy Bell et al., ACM Computing Surveys, Vol. 21, No. 4).
A method of fixing the degree of context involves fixing the length (degree) of context that obtains a conditional probability of appearance. If the degree is degree 2, for example, the method involves registering context of degree 2, in which a source character is connected to the two immediately preceding characters, calculating the conditional probability of appearance p(Xt.vertline.Xt-2,Xt-1) of this context of degree 2 and then storing the same, where Xt represents the source character, and Xt-1, Xt-2 respectively represent the immediately preceding first and second characters.
Blending contexts (blending degrees in a blended model) is a method of extending the degree of registered context in dependence upon entered data without fixing the degree of context. The sequential registration method is known as a method of extending the degree of registered context. FIG. 26 is a diagram for describing a context tree registered by the sequential registration method in a case where the character string "cacbcaaabca" has been entered. The characters a, b, c initially are connected to "root", and the probabilities of appearance thereof initially are set.
FIG. 27 is a diagram for describing the sequential registration method in a case where the character string "FUJITSU" has been entered three consecutive times. Each of the characters F, U, J, I, T, S, U has been initially registered as encoding context (context of degree 0) [see (a) in FIG. 27]. If the initial character string "FUJITSU" is entered under these conditions, the following contexts are registered, as indicated at (b) in FIG. 27:
If the next character string "FUJITSU" is entered under these conditions, encoding is performed with the registered contexts of (b) serving as the encoding contexts. Further, the following contexts are registered, in the manner indicated at (d):
If the next character string "FUJITSU" is entered under these conditions, encoding is performed with the registered contexts of (d) serving as the encoding context. Further, the following contexts are registered, as indicated at (e):
Thereafter, and in similar fashion, context is extended in accordance with sequential registration one degree at a time whenever a character is entered.
FIG. 28 is a processing flowchart illustrating a blended model compression method according to the prior art.
The first step in FIG. 28 is to initialize a character number t to 0 (step 101). The character number t is then incremented and a character Xt, which is the t-th character, is entered (step 102). The degree n is then made the degree N of context of maximum length (step 103).
This is followed by step 104, at which it is determined whether the context X(t-n,t-1) has been registered in a context tree. It should be noted that the context X(t-n,t-1) is a character string {Xt-n, Xt-n+1, . . . , Xt-1}. If the context X(t-n,t-1) has not been registered, the degree n is decremented (step 105) and it is determined whether context shortened by one character has been registered (step 104).
If the context X(t-n,t-1) has been registered, it is determined whether a combination of the context X(t-n,t-1) and a source character Xt to be encoded is present in the context tree (step 106). If the combination is not present in the context tree, an escape code (ESC code) that follows the context X(t-n,t-1) is encoded and outputted (step 107), after which processing from step 105 onward is repeated.
If the combination of the context X(t-n,t-1) and a source character Xt is present in the context tree, then the character Xt is encoded and outputted using the probability that the source character Xt will appear following the context X(t-n, t-1) (step 108). It is then determined whether the encoding of all data is finished (step 109). If encoding is not finished, the program returns to step 102 so that the above-described processing is repeated with regard to the next source character. It should be noted that processing for sequential registration of the context tree is carried out in parallel with above-described compressive encoding processing.
FIG. 29 is a processing flowchart illustrating a blended model restoration method according to the prior art.
The first step in FIG. 29 is to initialize the character number t to 0 (step 121). The character number t is then incremented (step 122) and the degree n is then made the degree N of context of maximum length (step 123).
This is followed by step 124, at which it is determined whether the context X(t-n,t-1) has been registered in a context tree. It should be noted that the context X(t-n,t-1) is n-number of the latest character strings {Xt-n, Xt-n+1, . . . , Xt-1} already restored. If the context X(t-n,t-1) has not been registered, the degree n is decremented (step 125) and it is determined whether context shortened by a character has been registered (step 124). If the context X(t-n,t-1) has been registered, the t-th code is restored to a character code with the context X(t-n, t-1) serving as the condition (step 126).
Next, it is determined whether the restored character code is an ESC code (step 127). If the character code is the ESC code, then processing from step 125 onward is repeated. If the character code is not the ESC code, on the other hand, the restored character code is outputted (step 128). After the character code is outputted, it is determined whether reproduction processing is finished with regard to all data (step 129). If processing is not finished, the program returns to step 122 and the above-described processing is repeated for the next code. It should be noted that processing for sequential registration of the context tree is carried out in parallel with above-described restoration processing.
Thus, in data compression/restoration according to the blended model, a conditional probability of appearance (or the code per se) of each character is stored, inclusive of an ESC code indicating that registration is unfinished, for each and every context, and codes are outputted while degree of context is decremented one at a time until the character is compressed. Similarly, at the time of restoration, character codes are restored while degree is decremented one at a time until the character code is restored.
When context is lengthened (i.e., when the degree of context is enlarged) in a blended model, the following drawbacks arise:
With the conventional blended model, therefore, there are limitations in terms of improving compression/restoration speed and compression ratio and in terms of utilizing memory effectively.